home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Presentations / Presentations ’96 / Papers ’96 / Book of Practical Objects / BasicObjects ƒ / TreeNode.cp < prev    next >
Encoding:
Text File  |  1996-04-29  |  7.4 KB  |  357 lines  |  [TEXT/CWIE]
  1. #include "TreeNode.h"
  2. #include <stdio.h>
  3.  
  4.     TreeNode::TreeNode(void* theKey)
  5. {
  6.     fNodeKey = theKey;
  7.     fNodeData = nil;
  8.     
  9.     fParent = nil;
  10.     fLeftChild = nil;
  11.     fRightChild = nil;
  12.  
  13.     fLeftChildCount = 0;
  14.     fRightChildCount = 0;
  15. }
  16.  
  17.  
  18.     TreeNode::TreeNode(void* theKey, void* theData)
  19. {
  20.     fNodeKey = theKey;
  21.     fNodeData = theData;
  22.     
  23.     fParent = nil;
  24.     fLeftChild = nil;
  25.     fRightChild = nil;
  26.  
  27.     fLeftChildCount = 0;
  28.     fRightChildCount = 0;
  29.  
  30. }
  31.  
  32.  
  33.     TreeNode::~TreeNode(void)
  34. {
  35.  
  36. }
  37.  
  38.  
  39. // Insert node is non-recursive. Doing it this way simplifies the code since I
  40. // need to find the rood before doing insertion. This allows any node in the 
  41. // tree to take a new key and data for insertion, instead of limiting the insertion
  42. // to start only from the root of the entire tree. This allows us to guarantee that
  43. // the key remians unique to the entire tree.
  44. // Override this method if you want non-unique keys, or a different insertion order.
  45. TreeNode*    TreeNode::InsertNode(void* theKey, void* theData)
  46. {
  47.     TreeNode*    currentNode;
  48.     TreeNode*    newNode;
  49.     short        howToGo;
  50.     Boolean        insertFound = false;
  51.     
  52.     if (fParent == nil)
  53.         currentNode = this;
  54.     else
  55.         currentNode = this->GetRoot();
  56.     
  57.     printf("TreeRoot = %d\n", (long) currentNode->GetNodeKey());
  58.     
  59.     while (!insertFound)
  60.     {
  61.         howToGo = currentNode->CompareToNodeKey(theKey);
  62.         if (howToGo < 0)    // The new key is smaller than the node key, check left
  63.         {
  64.             if (currentNode->fLeftChild != nil)
  65.             {
  66.                 currentNode = currentNode->fLeftChild;
  67.                 printf("Moving left to node %d\n", (long) currentNode->GetNodeKey());
  68.             }
  69.             else {        // Insert it to the left
  70.                     printf("inserting on left\n");
  71.                     insertFound = true;
  72.                     howToGo = -1;        // Tell me to insert to the left of the current node
  73.                  }
  74.         }
  75.         else if (howToGo > 0)
  76.              {
  77.                 if (currentNode->fRightChild != nil)
  78.                 {
  79.                     currentNode = currentNode->fRightChild;
  80.                     printf("Moving right to node %d\n", (long) currentNode->GetNodeKey());
  81.                 }
  82.                 else {        // Insert it to the right
  83.                         printf("inserting on right\n");
  84.                         insertFound = true;
  85.                         howToGo = 1;        // Tell me to insert to the left of the current node
  86.                      }
  87.              }
  88.     }
  89.     
  90.     if (howToGo == 0)        // if 0, we found an identical key and don't want to insert
  91.     {
  92.         newNode = nil;
  93.     }
  94.     else {
  95.             newNode = new TreeNode(theKey, theData);
  96.             if (howToGo < 0)
  97.                 currentNode->fLeftChild = newNode;
  98.             else
  99.                 currentNode->fRightChild = newNode;
  100.             
  101.             newNode->fParent = currentNode;
  102.             
  103.             // Now the last thing to do is to propagate the addition upwards in the counts
  104.             currentNode->fLeftChildCount++;    // Goes from 0 to 1
  105.             while (currentNode != nil)
  106.             {
  107.                 if (currentNode->fParent != nil)
  108.                 {
  109.                     if (currentNode->fParent->fLeftChild == currentNode)    // up the left child count
  110.                         currentNode->fParent->fLeftChildCount++;
  111.                     else
  112.                         currentNode->fParent->fRightChildCount++;
  113.                 }
  114.                     
  115.                 currentNode = currentNode->fParent;
  116.             }
  117.          }
  118.     
  119.     return (newNode);
  120. }
  121.  
  122.  
  123.     
  124. void*    TreeNode::GetNodeKey(void)
  125. {
  126.     return (fNodeKey);
  127. }
  128.  
  129.  
  130. void*    TreeNode::GetNodeData(void)
  131. {
  132.     return (fNodeData);
  133. }
  134.  
  135.  
  136. void    TreeNode::SetNodeData(void* theData)
  137. {
  138.     fNodeData = theData;
  139. }
  140.  
  141.  
  142.  
  143. TreeNode*    TreeNode::FindKeyNode(void* searchKey)
  144. {
  145.     TreeNode*    theNode = GetRoot();
  146.     short        result;
  147.     
  148.     while (theNode != nil)
  149.     {
  150.         result = theNode->CompareToNodeKey(searchKey);
  151.         if (result == 0)        // Found it, so just return the current node
  152.             return (theNode);
  153.         else if (result < 0)    // Check the left side branch
  154.                  theNode = theNode->fLeftChild;
  155.              else                // Otherwise try the right branch
  156.                  theNode = theNode->fRightChild;
  157.     }
  158.     
  159.     return (theNode);            // If we ran out of nodes without matching
  160.                                 // this returns nil;
  161. }
  162.  
  163.  
  164. // This code is essentially identical to FindKeyNode, but if somebody
  165. // wants to override it for some specific purpose, they can.
  166. TreeNode*    TreeNode::FindDataNode(void* searchData)    // Returns FIRST instance of searchData
  167. {
  168.     TreeNode*    theNode = GetRoot();
  169.     short        result;
  170.     
  171.     while (theNode != nil)
  172.     {
  173.         result = theNode->CompareToNodeData(searchData);
  174.         if (result == 0)        // Found it, so just return the current node
  175.             return (theNode);
  176.         else if (result < 0)    // Check the left side branch
  177.                  theNode = theNode->fLeftChild;
  178.              else                // Otherwise try the right branch
  179.                  theNode = theNode->fRightChild;
  180.     }
  181.     
  182.     return (theNode);            // If we ran out of nodes without matching
  183.                                 // this returns nil;
  184.  
  185. }
  186.  
  187.  
  188. long    TreeNode::GetChildCount(void)
  189. {
  190.     return (fLeftChildCount + fRightChildCount);
  191. }
  192.  
  193.  
  194. long    TreeNode::GetLeftChildCount(void)
  195. {
  196.     return (fLeftChildCount);
  197. }
  198.  
  199.  
  200. long    TreeNode::GetRightChildCount(void)
  201. {
  202.     return (fRightChildCount);
  203. }
  204.  
  205.  
  206.  
  207. TreeNode*    TreeNode::GetFirstNode(void)
  208. {
  209.     TreeNode*    leftmostNode;
  210.     
  211.     if (fParent == nil)
  212.         leftmostNode = GetLeftmostSubNode();
  213.     else
  214.         leftmostNode = GetRoot()->GetLeftmostSubNode();
  215.     
  216.     return (leftmostNode);
  217. }
  218.  
  219. // Return the next node in key order. We know that there are no unprocessed left children
  220. // for this node (since we are in-order) but there may be right children. If there
  221. // is a right child we need to move down its leftmost side
  222. TreeNode*    TreeNode::GetNextNode(void)
  223. {
  224.     TreeNode*    targetNode;
  225.     TreeNode*    curNode = nil;
  226.     Boolean        foundIt = true;
  227.  
  228.     // We know that this node has already been returned. So return a right
  229.     // right branch leftmost branch 
  230.     if (fRightChild != nil)
  231.     {
  232.         printf("getting right child subnode\n");
  233.         targetNode = fRightChild->GetLeftmostSubNode();
  234.     }
  235.     else {        // No right child, move up and see if we were the right child
  236.             curNode = this;
  237.             foundIt = false;
  238.             while (foundIt == false)
  239.             {
  240.                 if (curNode->fParent == nil)        // We were at the root of the tree, and no right node
  241.                 {
  242.                     targetNode = nil;    // Nothing move to traverse
  243.                     foundIt = true;
  244.                 }
  245.                 else {
  246.                         if (curNode->fParent->fRightChild == curNode)    // We were the right child
  247.                         {
  248.                             curNode = curNode->fParent;
  249.                             printf("this was right child, moving up to parent\n");
  250.                         }
  251.                         else {    // We were the left child, return the parent now
  252.                                 curNode = curNode->fParent;
  253.                                 printf("Moving up to parent %d\n", (long) curNode->GetNodeKey());
  254.                                 targetNode = curNode; // ->GetNextNode();
  255.                                 foundIt = true;
  256.                              }
  257.                      }
  258.             }
  259.           }
  260.     return (targetNode);
  261. }
  262.  
  263.  
  264. TreeNode*    TreeNode::GetPreviousNode(void)
  265. {
  266.  
  267. }
  268.  
  269.  
  270. TreeNode*    TreeNode::GetRoot(void)
  271. {
  272.     TreeNode*    aNode = this;
  273.     
  274.     while (aNode->fParent != nil)
  275.         aNode = aNode->fParent;
  276.     
  277.     return (aNode);
  278. }
  279.  
  280.  
  281. void    TreeNode::PruneBranch(void)    // Remove this branch and sub-branches from the tree.
  282. {
  283.     if (fParent->fLeftChild == this)
  284.         fParent->fLeftChild = nil;
  285.     else
  286.         fParent->fRightChild = nil;
  287. }
  288.  
  289.  
  290. TreeNode*    TreeNode::GetLeftmostSubNode(void)
  291. {
  292.     TreeNode*    curNode = this;
  293.     
  294.     while (curNode->fLeftChild)
  295.     {
  296.         curNode = curNode->fLeftChild;
  297.     }
  298.  
  299.     return (curNode);
  300. }
  301.  
  302.  
  303. void    TreeNode::InsertChildLeft(TreeNode *nodePtr)
  304. {
  305.  
  306. }
  307.  
  308.  
  309. void    TreeNode::InsertChildRight(TreeNode *nodePtr)
  310. {
  311.  
  312. }
  313.  
  314.  
  315. void    TreeNode::DeleteChildLeft()
  316. {
  317.  
  318. }
  319.  
  320.  
  321. void    TreeNode::DeleteChildRight()
  322. {
  323.  
  324. }
  325.  
  326.  
  327. // Returns -1 if compareData < fNodeData, 0 if equal, and 1 if compareData > fNodeData
  328. // For the reusable class, I'm abusing void* and using it to hold a long value
  329. short    TreeNode::CompareToNodeKey(void* compareKey)
  330. {
  331.     short    result;
  332.  
  333.     if (compareKey < fNodeKey)
  334.         result = -1;
  335.     else if (compareKey > fNodeKey)
  336.             result = 1;
  337.          else
  338.              result = 0;
  339.  
  340.     return (result);
  341. }
  342.  
  343.  
  344. short    TreeNode::CompareToNodeData(void* compareData)
  345. {
  346.     short    result;
  347.  
  348.     if (compareData < fNodeData)
  349.         result = -1;
  350.     else if (compareData > fNodeData)
  351.             result = 1;
  352.          else
  353.              result = 0;
  354.  
  355.     return (result);
  356. }
  357.